This invention relates to voxel-based systems and more particularly to a system for rapidly deforming volumetric inhomogenous objects.
Surgical simulation requires interactive modeling and visualization of complex, 3D anatomical structures. For example, surgery of the abdomen involves probing and cutting through organs and tissues that have complex shapes and material properties. Because modeling the deformation and cutting of tissue requires a representation of interior structure. Volumetric object representation is well suited to surgical simulation. A volumetric representation can incorporate detailed information about internal anatomical or physiological structure. This detailed information can be used to model tissue deformation more accurately than a model which represents the object surface and assumes a homogeneous interior.
In the past, a so-called 3D ChainMail algorithm has been developed for rapid deformation of homogenous objects as described by S. Gibson xe2x80x9c3D ChainMail: A fast algorithm for Deforming Volumetric Objectsxe2x80x9d Proceeding 1997 Synopsis on Interactive 3D Graphics pp. 149-154, Providence R.I. USA, 1997. In this algorithm, links between sampled data elements are established and characteristics of these links are defined. The links are such that an element is moved only if it needs to be which eliminates calculating movement of elements not affected by the movement of the selected element. The 3D ChainMail algorithm in one embodiment performs simple deformation calculations for each element of the graphical object to be deformed such that when the object is manipulated, the object stretches or contracts through the movement of neighboring elements only if a maximum or minimum preset distance is exceeded between the moved element and its neighbor.
While link characteristics are relatively easy to establish for homogenous materials, the problem is more complex for inhomogenous materials. Modeling of inhomogenous materials is important in applications ranging from image processing to virtual reality. In surgical simulation, for example, 3D ChainMail can be used for tissue modeling. Since tissue, in general, is not homogenous, techniques must be developed to take into account the speeds of propagation in inhomogenous materials.
In the subject invention, the 3D ChainMail algorithm is enhanced based on a physical model of how information is propagated through a body by passing it from one element to another. To achieve correct propagation of information in inhomogenous material, two basic concepts are introduced.
First, in ChainMail the material constraints determine the xe2x80x9cstiffnessxe2x80x9d of a connection between two neighbors. To model inhomogenous material, different material constraints are assigned to different elements.
Secondly, the order in which neighbors of moved elements are considered for a move determines where in the body information is propagated first. The processing order can therefore be used to model different, direction-dependent propagation speeds in the material.
After moving an element, its neighbors are examined to determine whether any constraint has been violated. The constraints between two neighbors are the sum of the contributions from the two affected elements. Note, affected elements are those which are neighbors of a moved element. If a constraint was violated, the neighbor with the largest constraint violation is processed first. This is equivalent to processing neighbors in the order in which their constraints were violated. By always following this order, it is guaranteed that the information follows the xe2x80x9cstiffestxe2x80x9d links.
In summary, an improvement to a voxel-based system to permit rapidly deforming volumetric objects made up of inhomogeneous material includes providing different material constraints assigned to different elements, with the constraints of a link between two neighboring elements being calculated from contributions of the two affected elements. The order in which neighbors of moved element are considered for a move determines where in the body information is propagated first. The processing order can therefore be used to model different direction-dependent propagation speeds in the material.